手写堆（Heap）

以下是使用 JavaScript 实现堆（Heap）的代码，支持自定义比较函数以创建最大堆或最小堆：

class Heap {
  constructor(compare = (a, b) => a < b) {
    this.compare = compare; // 比较函数，决定堆的类型（默认最小堆）
    this.heap = [];
  }

  // 插入元素
  insert(value) {
    this.heap.push(value);
    this._siftUp(this.heap.length - 1);
  }

  // 弹出堆顶元素
  extract() {
    if (this.heap.length === 0) return null;
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this._siftDown(0);
    }
    return top;
  }

  // 查看堆顶元素
  peek() {
    return this.heap.length === 0 ? null : this.heap[0];
  }

  // 获取堆大小
  size() {
    return this.heap.length;
  }

  // 判断堆是否为空
  isEmpty() {
    return this.heap.length === 0;
  }

  // 上浮操作
  _siftUp(index) {
    let current = index;
    while (current > 0) {
      const parent = Math.floor((current - 1) / 2);
      if (this.compare(this.heap[current], this.heap[parent])) {
        [this.heap[current], this.heap[parent]] = [this.heap[parent], this.heap[current]];
        current = parent;
      } else {
        break;
      }
    }
  }

  // 下沉操作
  _siftDown(index) {
    let current = index;
    const length = this.heap.length;
    while (true) {
      const leftChild = 2 * current + 1;
      const rightChild = 2 * current + 2;
      let target = current;

      // 与左子节点比较
      if (leftChild < length && this.compare(this.heap[leftChild], this.heap[target])) {
        target = leftChild;
      }
      // 与右子节点比较
      if (rightChild < length && this.compare(this.heap[rightChild], this.heap[target])) {
        target = rightChild;
      }
      // 若需要交换，继续下沉
      if (target !== current) {
        [this.heap[current], this.heap[target]] = [this.heap[target], this.heap[current]];
        current = target;
      } else {
        break;
      }
    }
  }
}

使用示例

1. 最小堆（默认）

const minHeap = new Heap();
minHeap.insert(3);
minHeap.insert(1);
minHeap.insert(2);
console.log(minHeap.extract()); // 输出 1
console.log(minHeap.extract()); // 输出 2
console.log(minHeap.extract()); // 输出 3

2. 最大堆

const maxHeap = new Heap((a, b) => a > b);
maxHeap.insert(3);
maxHeap.insert(1);
maxHeap.insert(2);
console.log(maxHeap.extract()); // 输出 3
console.log(maxHeap.extract()); // 输出 2
console.log(maxHeap.extract()); // 输出 1

方法说明

• insert(value): 插入元素，并调整堆结构。
• extract(): 弹出堆顶元素，并调整堆结构。
• peek(): 查看堆顶元素（不删除）。
• size(): 返回堆的大小。
• isEmpty(): 判断堆是否为空。

实现细节

• 比较函数：通过构造函数传入，默认实现最小堆。例如， (a, b) => a < b 表示父节点应小于子节点。
• 数组存储：使用数组模拟完全二叉树，父子节点通过索引计算。
• 上浮与下沉：插入元素时执行上浮操作，弹出元素时执行下沉操作，确保堆的性质不变。